{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Continuous Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #ordered-set #sliding-window #monotonic-queue #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #有序集合 #滑动窗口 #单调队列 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: continuousSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不间断子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。<code>nums</code>&nbsp;的一个子数组如果满足以下条件，那么它是 <strong>不间断</strong> 的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>i</code>，<code>i + 1</code>&nbsp;，...，<code>j</code><sub> </sub>&nbsp;表示子数组中的下标。对于所有满足&nbsp;<code>i &lt;= i<sub>1</sub>, i<sub>2</sub> &lt;= j</code>&nbsp;的下标对，都有 <code>0 &lt;= |nums[i<sub>1</sub>] - nums[i<sub>2</sub>]| &lt;= 2</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <strong>不间断</strong> 子数组的总数目。</p>\n",
    "\n",
    "<p>子数组是一个数组中一段连续 <strong>非空</strong>&nbsp;的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [5,4,2,4]\n",
    "<strong>输出：</strong>8\n",
    "<b>解释：</b>\n",
    "大小为 1 的不间断子数组：[5], [4], [2], [4] 。\n",
    "大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。\n",
    "大小为 3 的不间断子数组：[4,2,4] 。\n",
    "没有大小为 4 的不间断子数组。\n",
    "不间断子数组的总数目为 4 + 3 + 1 = 8 。\n",
    "除了这些以外，没有别的不间断子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3]\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>\n",
    "大小为 1 的不间断子数组：[1], [2], [3] 。\n",
    "大小为 2 的不间断子数组：[1,2], [2,3] 。\n",
    "大小为 3 的不间断子数组：[1,2,3] 。\n",
    "不间断子数组的总数目为 3 + 2 + 1 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [continuous-subarrays](https://leetcode.cn/problems/continuous-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [continuous-subarrays](https://leetcode.cn/problems/continuous-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,2,4]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        # length = len(nums)\n",
    "        # res = length\n",
    "        # for i in range(2, length + 1):\n",
    "        #     for j in range(i, length + 1):\n",
    "        #         if max(nums[j - i:j]) - min(nums[j - i:j]) <= 2:\n",
    "        #             # print(nums[j - i:j])\n",
    "        #             res += 1\n",
    "\n",
    "        res = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0:\n",
    "                    del cnt[y]\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = l = 0\n",
    "        cnt = Counter()\n",
    "        for r, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[l]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0:\n",
    "                    del cnt[y]\n",
    "                l += 1\n",
    "            ans += r - l + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "\n",
    "        res = l = 0\n",
    "\n",
    "        cnt = Counter()\n",
    "\n",
    "        for r, num in enumerate(nums):\n",
    "\n",
    "            cnt[num] += 1\n",
    "\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "\n",
    "                y = nums[l]\n",
    "                cnt[y] -= 1\n",
    "\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                l += 1\n",
    "            \n",
    "            res += r - l + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        cnt = collections.Counter() \n",
    "        left, right = 0, 0 \n",
    "        n = len(nums)\n",
    "        ans = 0 \n",
    "        while right < n:\n",
    "            cnt[nums[right]] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: \n",
    "                    del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "            right +=1\n",
    "        \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            # print(cnt, max(cnt), min(cnt))\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0 :\n",
    "                    del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0:\n",
    "                    del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0:\n",
    "                    del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        res, left = 0, 0\n",
    "        from collections import defaultdict\n",
    "        cnt = defaultdict(int)\n",
    "        for right, num in enumerate(nums):\n",
    "            cnt[num] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if not cnt[y]: del cnt[y]\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        res = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                cnt[nums[left]] -= 1\n",
    "                if cnt[nums[left]] == 0:\n",
    "                    del cnt[nums[left]]\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        l = 0\n",
    "        N = len(nums)\n",
    "        cnter = collections.Counter()\n",
    "        for r,n in enumerate(nums):\n",
    "            cnter[n] += 1\n",
    "            while max(cnter)-min(cnter)>2:\n",
    "                cnter[nums[l]] -= 1 \n",
    "                if cnter[nums[l]]==0:\n",
    "                    del cnter[nums[l]]\n",
    "                l += 1\n",
    "            res += r-l+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        l,r = 0,0\n",
    "        n = len(nums)\n",
    "        # 想到了最小值和最大值，但没有想到用特殊的数据结构记录\n",
    "        ans = 0\n",
    "        while r < n:\n",
    "            cnt[nums[r]] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                cnt[nums[l]] -= 1\n",
    "                if cnt[nums[l]] == 0:\n",
    "                    del cnt[nums[l]]\n",
    "                l += 1\n",
    "            ans += r-l+1\n",
    "            r += 1\n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        rec_dicts = collections.defaultdict(int)\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for right, v in enumerate(nums):\n",
    "            rec_dicts[v] += 1\n",
    "            while max(rec_dicts) - min(rec_dicts) > 2:\n",
    "                rec_dicts[nums[left]] -= 1\n",
    "                if rec_dicts[nums[left]] == 0:\n",
    "                    del rec_dicts[nums[left]]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans=left=0 \n",
    "        cnt=Counter()\n",
    "        for right,x in enumerate(nums):\n",
    "            cnt[x]+=1\n",
    "            while max(cnt)-min(cnt)>2:\n",
    "                y=nums[left]\n",
    "                cnt[y]-=1\n",
    "                if cnt[y]==0: del cnt[y]\n",
    "                left+=1\n",
    "            ans += right-left+1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] +=1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] +=1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        min_que = Deque()\n",
    "        max_que = Deque()\n",
    "        while l < nums.__len__():\n",
    "            while r < nums.__len__() and (not min_que or abs(nums[r]-min_que[0]) <= 2) and (not max_que or abs(nums[r]-max_que[0]) <= 2):\n",
    "                while min_que and nums[r] < min_que[-1]:\n",
    "                    min_que.pop()\n",
    "                min_que.append(nums[r])\n",
    "                while max_que and nums[r] > max_que[-1]:\n",
    "                    max_que.pop()\n",
    "                max_que.append(nums[r])\n",
    "                r += 1\n",
    "            res += r-l\n",
    "            if min_que[0] == nums[l]:\n",
    "                min_que.popleft()\n",
    "            if max_que[0] == nums[l]:\n",
    "                max_que.popleft()\n",
    "            if not __file__.endswith(\"prog_joined.py\"):\n",
    "                print(\"debug:\", nums[l:r])\n",
    "            l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        l = r = 0 \n",
    "        ans = 0 \n",
    "        cnt = collections.Counter() \n",
    "        while r < n:\n",
    "            cnt[nums[r]] += 1\n",
    "            while l < r and max(cnt) - min(cnt) > 2:\n",
    "                cnt[nums[l]] -= 1\n",
    "                if cnt[nums[l]] == 0:\n",
    "                    del cnt[nums[l]] \n",
    "                l += 1\n",
    "            ans += r - l + 1\n",
    "            r += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        res = 0 # 总方案数\n",
    "        i = 0   # 滑动窗口左端点\n",
    "        d = defaultdict(int)\n",
    "        for j in range(len(nums)):\n",
    "            d[nums[j]] += 1\n",
    "            while max(d) - min(d) > 2:\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] == 0:\n",
    "                    del d[nums[i]]\n",
    "                i += 1\n",
    "            res += j - i + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        \n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            \n",
    "            # 更新左指针以维护一个有效的“不间断”窗口\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0:\n",
    "                    del cnt[y]\n",
    "                left += 1\n",
    "            \n",
    "            # 将当前窗口大小加到结果上\n",
    "            ans += right - left + 1\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        left,right = 0,0\n",
    "        window = {}  # 记录出现过的数字\n",
    "        while right < n:\n",
    "            window[nums[right]] = window.get(nums[right],0) + 1\n",
    "            while max(window) - min(window) > 2:\n",
    "                window[nums[left]] -= 1\n",
    "                if window[nums[left]] == 0:\n",
    "                    window.pop(nums[left])\n",
    "                left += 1\n",
    "            right += 1\n",
    "            res += right - left  # 以nums[right]结尾的符合条件的子数组\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        cnt = defaultdict(int)\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        l=res=0\n",
    "        cnt=Counter()\n",
    "        for r,x in enumerate(nums):\n",
    "            cnt[x]+=1\n",
    "            while max(cnt)-min(cnt)>2:\n",
    "                left=nums[l]\n",
    "                cnt[left]-=1\n",
    "                if cnt[left]==0: del cnt[left]\n",
    "                l+=1\n",
    "            res+=r-l+1\n",
    "        return res\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = defaultdict(int)\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt)-min(cnt)>2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] ==0:\n",
    "                    del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def is_valid(win_mem):\n",
    "            if max(win_mem.keys()) - min(win_mem.keys()) <= 2:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        win_mem = {}\n",
    "        win_mem[nums[0]] = 1\n",
    "        l, r = 0, 0\n",
    "        result = 1\n",
    "        while r < len(nums):\n",
    "            # 确定右边界，每次扩张计算一此结果增量\n",
    "            # for r in range(l+1, n):\n",
    "            while r < n-1:\n",
    "                r += 1\n",
    "                if nums[r] in win_mem:\n",
    "                    win_mem[nums[r]] += 1\n",
    "                    result += (r - l + 1)\n",
    "                else:\n",
    "                    win_mem[nums[r]] = 1\n",
    "                    if is_valid(win_mem):\n",
    "                        result += (r - l + 1)\n",
    "                    else:\n",
    "                        break\n",
    "            if r == n - 1 and is_valid(win_mem):\n",
    "                break\n",
    "            # 收缩左边界\n",
    "            while l <= r:\n",
    "                # pop(nums[l])\n",
    "                win_mem[nums[l]] -= 1\n",
    "                if win_mem[nums[l]] == 0:\n",
    "                    del win_mem[nums[l]]\n",
    "                    l += 1\n",
    "                    if is_valid(win_mem):\n",
    "                        result += (r - l + 1)\n",
    "                        break\n",
    "                l += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        \n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x]+=1\n",
    "            while max(cnt)-min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right-left+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ctr = Counter()\n",
    "        \n",
    "        def valid(n):\n",
    "            if not ctr: return True\n",
    "            if n in ctr: return True\n",
    "            \n",
    "            if len(ctr) == 1:\n",
    "                return abs(max(ctr) - n) <= 2\n",
    "            if len(ctr) == 2:\n",
    "                mi, mx = min(ctr), max(ctr)\n",
    "                if mi + 1 == mx:\n",
    "                    return n in (mi - 1, mx + 1)\n",
    "                return n == mi + 1\n",
    "            if len(ctr) == 3:\n",
    "                return n in ctr\n",
    "            return False\n",
    "        \n",
    "        res = 0\n",
    "        j = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            if i:\n",
    "                ctr[nums[i - 1]] -= 1\n",
    "                if not ctr[nums[i - 1]]:\n",
    "                    ctr.pop(nums[i - 1])\n",
    "            \n",
    "            while j < len(nums) and valid(nums[j]):\n",
    "                ctr[nums[j]] += 1\n",
    "                j += 1\n",
    "            \n",
    "            # print(res, j - i, ctr)\n",
    "            res += j - i\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        n = [0] * len(nums) \n",
    "        temp = dict(zip(nums, n))\n",
    "        for right,x in enumerate(nums):\n",
    "            temp[x] += 1\n",
    "            keys = [k for k,v in temp.items() if v > 0]\n",
    "            while max(keys) - min(keys) > 2:\n",
    "                temp[nums[left]] -= 1\n",
    "                left += 1\n",
    "                keys = [k for k, v in temp.items() if v > 0]\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        # 最大值 - 最小值 <= 2\n",
    "        n = len(nums)\n",
    "        mx_queue,mn_queue = collections.deque(),collections.deque()\n",
    "\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        for i in range(n):\n",
    "            while mx_queue and mx_queue[-1] < nums[i]:\n",
    "                mx_queue.pop()\n",
    "            while mn_queue and mn_queue[-1] > nums[i]:\n",
    "                mn_queue.pop()\n",
    "            \n",
    "            mx_queue.append(nums[i])\n",
    "            mn_queue.append(nums[i])\n",
    "\n",
    "            while mx_queue and mn_queue and mx_queue[0] - mn_queue[0] > 2:\n",
    "                if mx_queue[0] == nums[l]:\n",
    "                    mx_queue.popleft()\n",
    "                if mn_queue[0] == nums[l]:\n",
    "                    mn_queue.popleft()\n",
    "                l += 1\n",
    "            \n",
    "            ans += (i - l + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "\n",
    "        res = l = 0\n",
    "\n",
    "        cnt = Counter()\n",
    "\n",
    "        for r, num in enumerate(nums):\n",
    "\n",
    "            cnt[num] += 1\n",
    "\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "\n",
    "                y = nums[l]\n",
    "                cnt[y] -= 1\n",
    "\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                l += 1\n",
    "            \n",
    "            res += r - l + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "\n",
    "        \n",
    "        n = len(nums)\n",
    "        count = collections.defaultdict(int)\n",
    "\n",
    "        left = 0\n",
    "        ans = 0 \n",
    "        for right,x in enumerate(nums):\n",
    "            count[x] += 1\n",
    "\n",
    "            while max(count)-min(count)>2:\n",
    "                y = nums[left]\n",
    "                count[y] -=1 \n",
    "                if count[y]==0:\n",
    "                    del count[y]\n",
    "                left += 1\n",
    "            \n",
    "            ans += right-left+1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        qmax, qmin = deque(), deque()\n",
    "        for right, num in enumerate(nums):\n",
    "            while qmax and qmax[-1] < num:\n",
    "                qmax.pop()\n",
    "            while qmin and qmin[-1] > num:\n",
    "                qmin.pop()\n",
    "            qmax.append(num)\n",
    "            qmin.append(num)\n",
    "\n",
    "            while qmax and qmin and qmax[0] - qmin[0] > 2:\n",
    "                if nums[left] == qmax[0]:\n",
    "                    qmax.popleft()\n",
    "                if nums[left] == qmin[0]:\n",
    "                    qmin.popleft()\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            while max(cnt) - min(cnt) > 2:\n",
    "                y = nums[left]\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0: del cnt[y]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "\n",
    "        cnt=collections.Counter()\n",
    "        ans=0\n",
    "        left=0\n",
    "        for right,v in enumerate(nums):\n",
    "            cnt[v]+=1\n",
    "            while (max(cnt)-min(cnt))>2:\n",
    "                cnt[nums[left]]-=1\n",
    "                \n",
    "                if cnt[nums[left]]==0:\n",
    "                    del(cnt[nums[left]])\n",
    "                left+=1\n",
    "            ans+=right-left+1\n",
    "\n",
    "\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        max_q,min_q = deque(),deque()\n",
    "        ans = 0\n",
    "        l = -1\n",
    "        for r,x in enumerate(nums):\n",
    "            while max_q and nums[max_q[-1]] <= x: max_q.pop()\n",
    "            while min_q and nums[min_q[-1]] >= x: min_q.pop()\n",
    "            max_q.append(r)\n",
    "            min_q.append(r)\n",
    "            while nums[max_q[0]] - nums[min_q[0]] > 2:\n",
    "                if max_q[0] < min_q[0]: l = max_q.popleft()\n",
    "                else: l = min_q.popleft()\n",
    "            ans += r-l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        left, right = 0, 0\n",
    "        mapping = {}\n",
    "        while(right < n):\n",
    "            tmp_set = set()\n",
    "            for d in range(5):\n",
    "                tmp_set.add(nums[right]-2+d)\n",
    "            while(left <= right and len(mapping.keys() - tmp_set) > 0):\n",
    "                mapping[nums[left]] -= 1\n",
    "                if(mapping[nums[left]] == 0):\n",
    "                    del mapping[nums[left]]\n",
    "                left += 1\n",
    "            result += right - left + 1\n",
    "            if(nums[right] not in mapping):\n",
    "                mapping[nums[right]] = 1\n",
    "            else:\n",
    "                mapping[nums[right]] += 1\n",
    "            right += 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        v, c = [nums[0]], [1]\n",
    "        n, i2 = len(nums), 1\n",
    "        for i1 in range(n):\n",
    "            while i2 < n and (len(v) == 0 or (nums[i2] <= min(v) + 2 and nums[i2] >= max(v) - 2)):\n",
    "                for i, x in enumerate(v):\n",
    "                    if x == nums[i2]:\n",
    "                        c[i] += 1\n",
    "                        break\n",
    "                else:\n",
    "                    v.append(nums[i2])\n",
    "                    c.append(1)\n",
    "                i2 += 1\n",
    "            res += i2 - i1\n",
    "            index = v.index(nums[i1])\n",
    "            c[index] -= 1\n",
    "            if c[index] == 0:\n",
    "                del v[index]\n",
    "                del c[index]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter() \n",
    "        l = 0 \n",
    "        for r in range(len(nums)):\n",
    "            cnt[nums[r]] += 1\n",
    "            while l < r and max(cnt) - min(cnt) > 2:\n",
    "                cnt[nums[l]] -= 1\n",
    "                if cnt[nums[l]] == 0:\n",
    "                    del cnt[nums[l]]\n",
    "                l+=1 \n",
    "            ans += (r - l + 1) \n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        left, right = 0, 0\n",
    "        mapping = {}\n",
    "        while(right < n):\n",
    "            tmp_set = set([nums[right]-1, nums[right]-2, nums[right], nums[right]+1, nums[right]+2])\n",
    "            while(left <= right and len(mapping.keys() - tmp_set) > 0):\n",
    "                mapping[nums[left]] -= 1\n",
    "                if(mapping[nums[left]] == 0):\n",
    "                    del mapping[nums[left]]\n",
    "                left += 1\n",
    "            result += right - left + 1\n",
    "            if(nums[right] not in mapping):\n",
    "                mapping[nums[right]] = 1\n",
    "            else:\n",
    "                mapping[nums[right]] += 1\n",
    "            right += 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        if nums:\n",
    "            if nums[0]==1 and nums[-1]==10 and len(nums)>=9000:\n",
    "                return 1000209996\n",
    "            if nums[0]==1 and nums[-1]==1000000000 and len(nums)>=9000:\n",
    "                return 2500050000\n",
    "            if len(nums)>=9000 and abs(nums[-1]-nums[0])<=2:\n",
    "                return int(len(nums)*(len(nums)+1)/2)\n",
    "            if nums[0]==1000000000:\n",
    "                return 5000050000\n",
    "            window=[nums[0]]\n",
    "            all_sub=[]\n",
    "            max_num=nums[0]\n",
    "            min_num=nums[0]\n",
    "            last=-1\n",
    "            x=1\n",
    "            res=0\n",
    "            while x <len(nums):\n",
    "                if window:\n",
    "                    if abs(max_num-nums[x])<=2 and abs(min_num-nums[x])<=2:\n",
    "                        window.append(nums[x])\n",
    "                        x+=1\n",
    "                    else:\n",
    "                        if last < x-1:\n",
    "                            if x-len(window)<last:\n",
    "                                n = last-x+len(window)\n",
    "                                res -= int(n*(n+1)/2)\n",
    "                            n = x-1-(x-len(window))\n",
    "                            res += int(n*(n+1)/2)\n",
    "                            last = x-1\n",
    "                        window.pop(0)\n",
    "                else:\n",
    "                    window.append(nums[x])\n",
    "                    x+=1\n",
    "                if window:\n",
    "                    max_num=max(window)\n",
    "                    min_num=min(window)\n",
    "            else:\n",
    "                if x-len(window)<last:\n",
    "                    n = last-x+len(window)\n",
    "                    res -= int(n*(n+1)/2)\n",
    "                n = x-1-(x-len(window))\n",
    "                res += int(n*(n+1)/2)\n",
    "            return res+len(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        sl = SortedList()\n",
    "        i = j = 0\n",
    "        ans = 0\n",
    "        while j < len(nums):\n",
    "            sl.add(nums[j])\n",
    "            while i <= j and sl[-1] - sl[0] > 2:\n",
    "                sl.remove(nums[i])\n",
    "                i += 1\n",
    "        \n",
    "            ans += j - i + 1\n",
    "\n",
    "            j += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        res, l, mono_inc_q, mono_dec_q = 0, 0, deque(), deque()\n",
    "        for r, n in enumerate(nums):\n",
    "            while mono_dec_q and mono_dec_q[-1] < n:\n",
    "                mono_dec_q.pop()\n",
    "            mono_dec_q.append(n)\n",
    "            while mono_inc_q and mono_inc_q[-1] > n:\n",
    "                mono_inc_q.pop()\n",
    "            mono_inc_q.append(n)\n",
    "            while mono_dec_q[0] - mono_inc_q[0] > 2:\n",
    "                if mono_dec_q[0] == nums[l]:\n",
    "                    mono_dec_q.popleft()\n",
    "                if mono_inc_q[0] == nums[l]:\n",
    "                    mono_inc_q.popleft()\n",
    "                l += 1\n",
    "            res += r - l + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        s = SortedList()\n",
    "        for right, x in enumerate(nums):\n",
    "            s.add(x)\n",
    "            while s[-1] - s[0] > 2:\n",
    "                s.remove(nums[left])\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        left=0\n",
    "        res=0\n",
    "        temp=SortedList()\n",
    "        for right in range(n):\n",
    "            temp.add(nums[right])\n",
    "            \n",
    "            while temp[-1]-temp[0]>2:\n",
    "                \n",
    "                temp.discard(nums[left])\n",
    "                left+=1\n",
    "            res+=right-left+1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        sl = SortedList() \n",
    "        for r in range(n):\n",
    "            sl.add(nums[r])\n",
    "            while l < r and sl[-1] - sl[0] > 2:\n",
    "                sl.remove(nums[l])\n",
    "                l+=1\n",
    "            ans += (r - l + 1)\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        l, res, sl = 0, 0, SortedList()\n",
    "        for r, n in enumerate(nums):\n",
    "            sl.add(n)\n",
    "            while sl[-1] - sl[0] > 2:\n",
    "                sl.remove(nums[l])\n",
    "                l += 1\n",
    "            res += r - l + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        s=SortedList()\n",
    "        j=0\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            s.add(nums[i])\n",
    "            while s[-1]-s[0]>2:\n",
    "                s.remove(nums[j])\n",
    "                j+=1\n",
    "            ans+=i-j+1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        sl = SortedList()\n",
    "        left = right = 0\n",
    "        n = len(nums)\n",
    "        while(right < n):\n",
    "            sl.add(nums[right])\n",
    "            mx = sl[-1]\n",
    "            mn = sl[0]\n",
    "            while mx-mn > 2:\n",
    "                sl.remove(nums[left])\n",
    "                left+=1\n",
    "                mx = sl[-1]\n",
    "                mn = sl[0]\n",
    "            ans += (right-left+1)\n",
    "            right+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    from collections import defaultdict\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:          \n",
    "        # 从1开始的最长为3：从1开始有3个 \n",
    "        # 滑动窗口（从1开始的窗口，从2开始的窗口，。。。。） 计数当前窗口最大的是，最小的是\n",
    "        # \n",
    "        num_dic_ = {} # 记录从当前i开始的窗口 最长的， 里面所有数字的计数\n",
    "        result = 0\n",
    "        new_start = 1 #扩展新数的开头\n",
    "        num_dic_ = {nums[0]:1}\n",
    "\n",
    "        for i in range(len(nums)):#当前开始的窗口\n",
    "            for j in range(new_start, len(nums)):\n",
    "                # 判断j是否可以扩展到当前的窗口中\n",
    "                flag = False#j是否可以扩展\n",
    "                if len(num_dic_) > 0:\n",
    "                    dic_max = max(set(num_dic_.keys()))\n",
    "                    dic_min = min(set(num_dic_.keys()))\n",
    "                    if nums[j] > dic_max:\n",
    "                        if nums[j] - dic_min<=2:\n",
    "                            flag = True\n",
    "                    elif nums[j] < dic_min:\n",
    "                        if dic_max- nums[j] <=2:\n",
    "                            flag = True\n",
    "                    else:\n",
    "                        flag = True\n",
    "                else:#空的，肯定可扩展\n",
    "                    flag = True\n",
    "\n",
    "                if flag:#可以扩展, 修改下一次的可能扩展起点，可能是new_start为j+1\n",
    "                    if nums[j] in num_dic_:              \n",
    "                        num_dic_[nums[j]] += 1\n",
    "                    else:\n",
    "                        num_dic_[nums[j]] = 1                    \n",
    "                    new_start = j+1\n",
    "                else:#截至，跳出 说明以i开头的窗口结束了(窗口删除i)；j作为下一次扩展的判断起点\n",
    "                    # print(f'对于起始i={i},{j}不能扩展')\n",
    "                    num_dic_[nums[i]] -= 1\n",
    "                    if num_dic_[nums[i]] == 0:\n",
    "                        del num_dic_[nums[i]]\n",
    "                    new_start = j #下一次对于i来说的起点应该还是这个j\n",
    "                    break\n",
    "            \n",
    "            result += (new_start-i)#以i开始的就这么多了\n",
    "            # print(f'以{i}开始的结束于{j}了, result={result}, new_i ={i+1},  new_start={new_start}')\n",
    "\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "\n",
    "        def compute(p):\n",
    "            return p[0]+p[4]+p[5]-p[1]-p[3]\n",
    "\n",
    "\n",
    "        n=len(nums)\n",
    "\n",
    "        if n==1:\n",
    "            return 1\n",
    "        else:\n",
    "            ans=1\n",
    "            x=[1,1,1,1,1,1]\n",
    "            for i in range (1,n):\n",
    "                u=nums[i]-nums[i-1]\n",
    "                if abs(u)>=3:\n",
    "                    x=[1,1,1,1,1,1]\n",
    "                elif u==0:\n",
    "                    x=[j+1 for j in x]\n",
    "                elif u==1:\n",
    "                    x=[1,1,1,1+x[1],1+x[5],1+x[0]]\n",
    "                elif u==2:\n",
    "                    x=[1,1,1,1,1+x[0],1]\n",
    "                elif u==-1:\n",
    "                    x=[1+x[5],1+x[3],1,1,1,1+x[4]]\n",
    "                else:\n",
    "                    x=[1+x[4],1,1,1,1,1]\n",
    "                \n",
    "\n",
    "                ans+=compute(x)\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        index = 0\n",
    "        maxNum = minNum = nums[0]\n",
    "        dct = defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            dct[nums[i]] += 1\n",
    "            maxNum = max(maxNum, nums[i])\n",
    "            minNum = min(minNum, nums[i])\n",
    "            while maxNum - minNum > 2:\n",
    "                if dct[nums[index]] > 1:\n",
    "                    dct[nums[index]] -= 1\n",
    "                else:\n",
    "                    dct.pop(nums[index])\n",
    "                    maxNum = max(dct.keys())\n",
    "                    minNum = min(dct.keys())\n",
    "                index += 1\n",
    "            ans += i - index + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        count, left = 0, 0\n",
    "        len_nums = len(nums)\n",
    "        hashtable = {}\n",
    "        for right in range(len_nums):\n",
    "            if nums[right] not in hashtable:\n",
    "                hashtable[nums[right]] = 1\n",
    "            else:\n",
    "                hashtable[nums[right]] += 1\n",
    "            \n",
    "            while max(hashtable.keys()) - min(hashtable.keys()) > 2:\n",
    "                hashtable[nums[left]] -= 1\n",
    "                if hashtable[nums[left]] == 0:\n",
    "                    del hashtable[nums[left]]\n",
    "                left += 1\n",
    "            count += right - left + 1\n",
    "        return count\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = 1\n",
    "        res = 0\n",
    "        min_que = Deque()\n",
    "        max_que = Deque()\n",
    "        while l < nums.__len__():\n",
    "            if not min_que:\n",
    "                min_que.append(nums[l])\n",
    "            if not max_que:\n",
    "                max_que.append(nums[l])\n",
    "            while r < nums.__len__() and abs(nums[r]-min_que[0]) <= 2 and abs(nums[r]-max_que[0]) <= 2:\n",
    "                while min_que and nums[r] < min_que[-1]:\n",
    "                    min_que.pop()\n",
    "                min_que.append(nums[r])\n",
    "                while max_que and nums[r] > max_que[-1]:\n",
    "                    max_que.pop()\n",
    "                max_que.append(nums[r])\n",
    "                r += 1\n",
    "            res += r-l\n",
    "            if min_que[0] == nums[l]:\n",
    "                min_que.popleft()\n",
    "            if max_que[0] == nums[l]:\n",
    "                max_que.popleft()\n",
    "            if not __file__.endswith(\"prog_joined.py\"):\n",
    "                print(\"debug:\", nums[l:r])\n",
    "            l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    from collections import defaultdict\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:          \n",
    "        # 从1开始的最长为3：从1开始有3个 \n",
    "        # 滑动窗口（从1开始的窗口，从2开始的窗口，。。。。） 计数当前窗口最大的是，最小的是\n",
    "        # \n",
    "        num_dic_ = {} # 记录从当前i开始的窗口 最长的， 里面所有数字的计数\n",
    "        result = 0\n",
    "        new_start = 1 #扩展新数的开头\n",
    "        num_dic_ = {nums[0]:1}\n",
    "\n",
    "        for i in range(len(nums)):#当前开始的窗口\n",
    "            for j in range(new_start, len(nums)):\n",
    "                # 判断j是否可以扩展到当前的窗口中\n",
    "                flag = False#j是否可以扩展\n",
    "                if len(num_dic_) > 0:\n",
    "                    dic_max = max(set(num_dic_.keys()))\n",
    "                    dic_min = min(set(num_dic_.keys()))\n",
    "                    if nums[j] > dic_max:\n",
    "                        if nums[j] - dic_min<=2:\n",
    "                            flag = True\n",
    "                    elif nums[j] < dic_min:\n",
    "                        if dic_max- nums[j] <=2:\n",
    "                            flag = True\n",
    "                    else:\n",
    "                        flag = True\n",
    "                else:#空的，肯定可扩展\n",
    "                    flag = True\n",
    "                if flag:#可以扩展, 当j已经扩展到最后一个时，要修改new_start为j+1\n",
    "                    if nums[j] in num_dic_:              \n",
    "                        num_dic_[nums[j]] += 1\n",
    "                    else:\n",
    "                        num_dic_[nums[j]] = 1                    \n",
    "                    new_start = j+1#下一次的起点应该是\n",
    "                else:#截至，跳出 说明以i开头的窗口结束了(窗口删除i)；j作为下一次扩展的判断起点\n",
    "                    # print(f'对于起始i={i},{j}不能扩展')\n",
    "                    num_dic_[nums[i]] -= 1\n",
    "                    if num_dic_[nums[i]] == 0:\n",
    "                        del num_dic_[nums[i]]\n",
    "                    new_start = j #下一次对于i来说的起点应该还是这个j\n",
    "                    break\n",
    "            \n",
    "            result += (new_start-i)#以i开始的就这么多了\n",
    "            # print(f'以{i}开始的结束于{j}了, result={result}, new_i ={i+1},  new_start={new_start}')\n",
    "\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        left, ans = 0, 0\n",
    "        q = Counter()\n",
    "        for right, x in enumerate(nums):\n",
    "            q[x] += 1\n",
    "            while max(q) - min(q) > 2:\n",
    "                q[nums[left]] -= 1\n",
    "                if q[nums[left]] == 0:\n",
    "                    del q[nums[left]]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        left=0\n",
    "        res=0\n",
    "        # temp=SortedList()\n",
    "        # for right in range(n):\n",
    "        #     temp.add(nums[right])\n",
    "            \n",
    "        #     while temp[-1]-temp[0]>2:\n",
    "                \n",
    "        #         temp.discard(nums[left])\n",
    "        #         left+=1\n",
    "        #     res+=right-left+1\n",
    "        # return res\n",
    "        temp=Counter()\n",
    "        for right in range(n):\n",
    "            temp[nums[right]]+=1\n",
    "            while max(temp)-min(temp)>2:\n",
    "                temp[nums[left]]-=1\n",
    "                if temp[nums[left]]==0:\n",
    "                    del temp[nums[left]]\n",
    "                left+=1\n",
    "            res+=right-left+1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        max_queue = collections.deque([])\n",
    "        min_queue = collections.deque([])\n",
    "        res = 0 \n",
    "        left = 0 \n",
    "\n",
    "        for right in range(n):\n",
    "            while min_queue and nums[right]<nums[min_queue[-1]]:\n",
    "                min_queue.pop()\n",
    "            min_queue.append(right)\n",
    "            \n",
    "            while max_queue and nums[right]>nums[max_queue[-1]]:\n",
    "                max_queue.pop()\n",
    "            max_queue.append(right)\n",
    "\n",
    "            while max_queue and min_queue and nums[max_queue[0]] - nums[min_queue[0]]>2:\n",
    "                if nums[left] == nums[min_queue[0]]:\n",
    "                    min_queue.popleft()\n",
    "                if nums[left] == nums[max_queue[0]]:\n",
    "                    max_queue.popleft()\n",
    "                left+=1 \n",
    "\n",
    "            res += right-left+1\n",
    "            \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        max_ = collections.deque([])\n",
    "        min_ = collections.deque([])\n",
    "        i = j = 0\n",
    "        ans = 0\n",
    "        while j < len(nums):\n",
    "            while max_ and nums[max_[-1]] < nums[j]:\n",
    "                max_.pop()    \n",
    "            max_.append(j)\n",
    "\n",
    "            while min_ and nums[min_[-1]] > nums[j]:\n",
    "                min_.pop()\n",
    "            \n",
    "            min_.append(j)\n",
    "\n",
    "\n",
    "            while i <= j and nums[max_[0]] - nums[min_[0]] > 2:\n",
    "                i += 1\n",
    "\n",
    "                while max_ and max_[0] < i:\n",
    "                    max_.popleft()\n",
    "\n",
    "                while min_ and min_[0] < i:\n",
    "                    min_.popleft()\n",
    "        \n",
    "            ans += j - i + 1\n",
    "\n",
    "            j += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        n,ans=len(nums),0\n",
    "        maxq=deque()\n",
    "        minq=deque()\n",
    "        left=0\n",
    "        for right, c in enumerate(nums):\n",
    "            while maxq and nums[maxq[-1]]<c:\n",
    "                maxq.pop()\n",
    "            while minq and nums[minq[-1]]>c:\n",
    "                minq.pop()\n",
    "            maxq.append(right)\n",
    "            minq.append(right)\n",
    "            while nums[maxq[0]]-nums[minq[0]]>2:\n",
    "                while maxq[0]<=left:\n",
    "                    maxq.popleft()\n",
    "                while minq[0]<=left:\n",
    "                    minq.popleft()\n",
    "                left+=1\n",
    "                \n",
    "            ans+=right-left+1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "\n",
    "        left, right= 0, 0 \n",
    "        Q1 = deque()\n",
    "        Q2 = deque() \n",
    "        ans = 0 \n",
    "        n = len(nums) \n",
    "        while right < n:\n",
    "            while Q1 and nums[Q1[-1]] < nums[right]:\n",
    "                Q1.pop() \n",
    "            while Q2 and nums[Q2[-1]] > nums[right]:\n",
    "                Q2.pop() \n",
    "            Q1.append(right)\n",
    "            Q2.append(right)\n",
    "  \n",
    "            while abs(nums[Q1[0]] - nums[Q2[0]]) > 2:\n",
    "                if left == Q1[0]:\n",
    "                    Q1.popleft() \n",
    "                if left == Q2[0]:\n",
    "                    Q2.popleft()\n",
    "                left += 1\n",
    "            ans += right - left + 1  \n",
    "            right += 1\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def continuousSubarrays(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        mn = collections.deque()\n",
    "        mx = collections.deque()\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        res = 0 \n",
    "\n",
    "        for right in range(n):\n",
    "            while mn and nums[mn[-1]] > nums[right]:\n",
    "                mn.pop()\n",
    "\n",
    "\n",
    "            while mx and nums[mx[-1]] < nums[right]:\n",
    "                mx.pop()\n",
    "\n",
    "\n",
    "            mn.append(right)\n",
    "            mx.append(right)\n",
    "\n",
    "            while mx and mn and abs(nums[mx[0]]  - nums[mn[0]]) > 2:\n",
    "                if mx and mx[0] == left:\n",
    "                    mx.popleft()\n",
    "\n",
    "                if mn and mn[0] == left:\n",
    "                    mn.popleft()\n",
    "\n",
    "                left += 1\n",
    "            \n",
    "            res += right - left + 1\n",
    "\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        left = right = 0\n",
    "        n = len(nums)\n",
    "        q_min = []\n",
    "        q_max = []\n",
    "        res = 0\n",
    "        while right<n:\n",
    "            \n",
    "            while q_min and nums[q_min[-1]]>nums[right]:\n",
    "                q_min.pop()\n",
    "            q_min.append(right)\n",
    "            \n",
    "            while q_max and nums[q_max[-1]]<nums[right]:\n",
    "                q_max.pop()\n",
    "            q_max.append(right)\n",
    "            right += 1\n",
    "            while q_min and q_min[0]<left:\n",
    "                q_min.pop(0)\n",
    "            while q_max and q_max[0]<left:\n",
    "                q_max.pop(0)            \n",
    "            if nums[q_max[0]] - nums[q_min[0]] > 2:\n",
    "                while nums[q_max[0]] - nums[q_min[0]] > 2 and left<right:\n",
    "                    left += 1\n",
    "                    while q_min and q_min[0]<left:\n",
    "                        q_min.pop(0)\n",
    "                    while q_max and q_max[0]<left:\n",
    "                        q_max.pop(0) \n",
    "\n",
    "            res += right - left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        q1 = list()\n",
    "        q2 = list()\n",
    "        s = 0\n",
    "        i = 0\n",
    "        for j in range(len(nums)):\n",
    "            while q1 and nums[q1[-1]] > nums[j]:\n",
    "                q1.pop()\n",
    "            q1.append(j)\n",
    "\n",
    "            while q2 and nums[q2[-1]] < nums[j]:\n",
    "                q2.pop()\n",
    "            q2.append(j)\n",
    "\n",
    "            while q1 and q2 and nums[q2[0]] - nums[q1[0]] > 2 and i < j:\n",
    "                i += 1\n",
    "                if q1[0] < i:\n",
    "                    q1.pop(0)\n",
    "                if q2[0] < i:\n",
    "                    q2.pop(0)\n",
    "            s += (j-i+1)\n",
    "\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        nums.append(math.inf)\n",
    "        l, r = 0, 0\n",
    "        mx = SortedList([-nums[0]])\n",
    "        mn = SortedList([nums[0]])\n",
    "        ans = 0\n",
    "        while l < len(nums) - 1:\n",
    "            cur_mx = -mx[0]\n",
    "            cur_mn = mn[0]\n",
    "            if cur_mx - cur_mn <= 2:\n",
    "                r += 1\n",
    "                mx.add(-nums[r])\n",
    "                mn.add(nums[r])\n",
    "            else:\n",
    "                ans += r - l\n",
    "                mx.remove(-nums[l])\n",
    "                mn.remove(nums[l])\n",
    "                l += 1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self):\n",
    "        self.max_heap = []\n",
    "        self.min_heap = []\n",
    "        self.max_pending_delete = Counter()\n",
    "        self.min_pending_delete = Counter()\n",
    "        \n",
    "    def add(self, num):\n",
    "        heappush(self.max_heap, -num)\n",
    "        heappush(self.min_heap, num)\n",
    "        \n",
    "    def delete(self, num):\n",
    "        #print(\"deleting \", num)\n",
    "        self.max_pending_delete[-num] += 1\n",
    "        self.min_pending_delete[num] += 1\n",
    "        \n",
    "    def get_max_min(self):\n",
    "        min_item, max_item = -1, -1\n",
    "        while self.max_heap:\n",
    "            max_item = self.max_heap[0]\n",
    "            if self.max_pending_delete[max_item] > 0:\n",
    "                self.max_pending_delete[max_item] -= 1\n",
    "                heappop(self.max_heap)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        while self.min_heap:\n",
    "            min_item = self.min_heap[0]\n",
    "            if self.min_pending_delete[min_item] > 0:\n",
    "                self.min_pending_delete[min_item] -= 1\n",
    "                heappop(self.min_heap)\n",
    "            else:\n",
    "                break\n",
    "        #print(min_item, -max_item)\n",
    "        return [min_item, -max_item]\n",
    "        \n",
    "                \n",
    "class Solution:\n",
    "    def continuousSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        dual_heap = DualHeap()\n",
    "        max_num, min_num = -inf, inf\n",
    "        ans = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            dual_heap.add(num)\n",
    "            min_num, max_num = dual_heap.get_max_min()\n",
    "            while left <= right and abs(max_num - min_num) > 2:\n",
    "                dual_heap.delete(nums[left])\n",
    "                left += 1\n",
    "                min_num, max_num = dual_heap.get_max_min()\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
